A storage system usually includes a host and a storage device, such as a non-volatile memory device. The storage device typically includes a plurality of physical blocks for storing data, and upon receiving a write command from the host, writes data to one of the physical blocks that is designated for writing the data. After the data are written to the storage device, the host may send a command (trim command) to invalidate the written data, for example when new data overwrite the written data. As a result, data written in the storage device may include both valid and invalid data.
When a capacity of free space in the physical blocks decreases to a certain level, one type of storage device carries out garbage collection with respect to some of the physical blocks in which data are written. Garbage collection is a process of copying all valid data from target physical blocks to another physical block, and erasing the target physical blocks. By erasing the target physical blocks, the target physical blocks can be used for new data writing.
However, even if the data written in the storage device is valid, in some cases the data may not need to be stored in the storage device any more. In such cases, it would be unnecessary to copy such data during the garbage collection, and copying such data would cause an increase in the latency of garbage collection.